package demo14;

import java.util.Arrays;

public class Solution {

//    //1.最长回文子串(动态规划)
//    public String longestPalindrome(String s) {
//        int len = s.length();
//        boolean[][] dp = new boolean[len][len];
//        //初始化
//        for(int i = 0; i < len; i++) {
//            dp[i][i] = true;
//        }
//        //递推
//        int left = 0;
//        int right = 0;
//        int maxResult = 0;
//        for(int i = len - 1; i >= 0; i--) {
//            for(int j = i + 1; j < len; j++) {
//                if(s.charAt(i) == s.charAt(j)) {
//                    if(j - i <= 1) {
//                        dp[i][j] = true;
//                    } else if(dp[i + 1][j - 1]) {
//                        dp[i][j] = true;
//                    }
//                }
//                if(dp[i][j] && j - i + 1 > maxResult) {
//                    maxResult = j - i + 1;
//                    left = i;
//                    right = j;
//                }
//            }
//        }
//        return s.substring(left, right + 1);
//    }

    //2.回文数(数学)
    public boolean isPalindrome(int x) {
        if(x < 0) {
            return false;
        }
        if(x < 10) {
            return true;
        }
        int ans = 0;//位数
        int tmp = x;
        while(tmp != 0) {
            tmp /= 10;
            ans++;
        }
        long left = (long) Math.pow(10, ans);//获得右边的除数
        long right = 10;//获得左边的除数
        while(left > right) {
            long valLeft = x % left / (left / 10L);
            long valRight = x % right / (right / 10L);
            if(valLeft != valRight) {
                return false;
            }
            left /= 10L;
            right *= 10L;
        }
        return true;
    }

    //最长递增子序列的个数(动态规划)
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        if(len <= 1) {
            return len;
        }
        int[] dp = new int[len];
        int[] count = new int[len];
        int maxLength = 0;
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        for(int i = 1; i < len; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    if(dp[j] + 1 > dp[i]) {
                        count[i] = count[j];
                    } else if(dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if(dp[i] > maxLength) {
                maxLength = dp[i];
            }
        }
        int result = 0;
        for(int i = 0; i < len; i++) {
            if(dp[i] == maxLength) {
                result += count[i];
            }
        }
        return result;
    }
}

class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.isPalindrome(1000000001);
    }
}
